1823F - Random Walk - CodeForces Solution

// So it's true... It's really true... If you don't want, you don't have to feel anything anymore!

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int mod = 998244353;
void upd(int& a, int b) { a = (a + b) % mod; }
int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return (a * 1ll * b) % mod; }
int pwr(int a, int b = mod - 2)
{
    if (!b) return 1;
    int h = pwr(a, b >> 1);
    h = mul(h, h);
    if (b & 1) h = mul(h, a);
    return h;
}

const int maxn = 2e5 + 5;
int ans[maxn];
vector<int> g[maxn];
int n, s, t;

vector<int> path;
bool dfs1(int u, int p = -1)
{
    if (u == t) return true;
    path.push_back(u);
    for (int v : g[u]) if (v != p && dfs1(v, u)) return true;
    path.pop_back();
    return false;
}
void dfs2(int x, int u, int p = -1)
{
    ans[u] = mul(x, g[u].size());
    for (int v : g[u]) if (v != p) dfs2(x, v, u);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s >> t;
    s--, t--;
    for (int i = 0, u, v; i < n - 1; i++) cin >> u >> v, g[--u].push_back(--v), g[v].push_back(u);
    dfs1(s);
    reverse(path.begin(), path.end());
    for (int i = 0; i < path.size(); i++)
    {
        int x = i + 1;
        ans[path[i]] = mul(x, g[path[i]].size());
        for (int j : g[path[i]])
        {
            if (j == t) continue;
            if (i && j == path[i - 1]) continue;
            if (i + 1 < path.size() && j == path[i + 1]) continue;
            dfs2(x, j, path[i]);
        }
    }
    ans[t] = 1;
    for (int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    return 0;
}